package homework;

public class HomeWork42 {
    TreeNode head,pre;
    public  TreeNode treeToDoublyList(TreeNode root) {
        if(root==null){
            return null;
        }
        dfs(root);
        while(root.left!=null){
            root=root.left;
        }
        head=root;
        TreeNode cur=root;
        while (cur.right!=null){
            cur=cur.right;
        }
        root.left=cur;
        cur.right=root;
        return head;
    }

    private void dfs(TreeNode root) {
        if(root==null){
            return;
        }
        dfs(root.left);
        if(pre!=null) pre.right=root;
        root.left=pre;
        pre=root;
        dfs(root.right);
    }
}
